package com.java.linkedlist;

import java.util.Stack;

public class SingLeLinkedListDemo {

    public static void main(String[] args) {

        //测试
        /**
         * 先创建节点
         */
        HeroNode heroNode = new HeroNode(1, "dc", "we");
        HeroNode heroNode1 = new HeroNode(2, "ch", "eat");
        HeroNode heroNode2 = new HeroNode(3, "lh", "sing");
        HeroNode heroNode3 = new HeroNode(4, "hk", "study");

        /**
         * 创建链表类
         */
        SingLeLinkedList singLeLinkedList = new SingLeLinkedList();

        /**
         * add加入：添加到链表最后
         */
//        singLeLinkedList.add(heroNode);
//        singLeLinkedList.add(heroNode1);
//        singLeLinkedList.add(heroNode2);
//        singLeLinkedList.add(heroNode3);

        /**
         * add:按顺序加入
         */
        singLeLinkedList.addByOrder(heroNode);
        singLeLinkedList.addByOrder(heroNode3);
        singLeLinkedList.addByOrder(heroNode1);
        singLeLinkedList.addByOrder(heroNode2);
        singLeLinkedList.addByOrder(heroNode3);

        //遍历显示当前链表中的全部数据
        singLeLinkedList.list();


        /**
         * 修改编号为2的节点
         */
        HeroNode heroNode4 = new HeroNode(2, "ab", "美丽");
        singLeLinkedList.update(heroNode4);
        System.out.println("修改后的链表情况");
        singLeLinkedList.list();


        /**
         * 根据编号删除节点
         */
        singLeLinkedList.delete(1);
        singLeLinkedList.delete(2);
        System.out.println("删除后的链表情况");
        singLeLinkedList.list();

        /**
         * 链表的有效节点个数
         */
        System.out.println(getLength(singLeLinkedList.getHead()));

        //倒数第k个节点
        System.out.println("测试倒数第k个节点");
        HeroNode lastIndexNode = findLastIndexNode(singLeLinkedList.getHead(), 2);
        System.out.println(lastIndexNode);

        /**
         * 测试链表反转
         */
        System.out.println("链表反转");
        reverseList(singLeLinkedList.getHead());
        singLeLinkedList.list();


        System.out.println("逆向打印");
        reversePrint(singLeLinkedList.getHead());


    }


    /**
     * 利用栈的数据结构，实现逆向打印,没有改变原链表的结构
     */
    public static void reversePrint(HeroNode head){
        if (head.next == null){
            return;//不能打印，为空
        }
        //创建一个栈，将各个节点压入栈
        Stack<HeroNode> stack = new Stack<>();
        HeroNode cur = head.next;//将 头节点的下一个赋给一个辅助的变量
        //将链表的所有节点压入栈中
        while (cur != null){
            stack.push(cur);
            cur = cur.next;//后移，可以压入下一个节点
        }
        //将栈中的节点打印
        while (stack.size() >0){
            System.out.println(stack.pop()); //出栈，先进后出
        }
    }


    /**
     * 链表反转，原链表的结构发生了变量
     * @param head
     */
    public static void reverseList(HeroNode head){
        //如果当前链表为空，或者只有一个节点，无需反转
        if (head.next == null || head.next.next == null){
            return;
        }

        //先定义一个辅助指针，帮助遍历
        HeroNode cur = head.next;
        HeroNode next = null;//指向当前节点的的下一个节点，因为取出一个后其指向就不存在了
        //定义新链表是带表头的
        HeroNode reverseHead = new HeroNode(0,"","");

        //遍历原来的链表，每遍历一个节点就将其取出，并放在新链表的头部
        while (cur != null){
            next = cur.next;//先暂时保存当前节点的下一个节点，后面需要使用
            cur.next = reverseHead.next;//将cur的下一个节点指向新的链表的最前端
            reverseHead.next = cur;//将cur 连接到新的链表上（总是赋给头部，之前的后移）
            cur = next;//让cur后移，
        }
        //实现单链表的反转
        head.next = reverseHead.next;

    }


    /**
     * 查找单列表的倒数第k个节点
     */
    //思路
    //1 编写一个方法，接收head节点，同时接收一个index
    //2 index 表示是倒数第 index个节点
    //3 先把链表从头到尾遍历，得到链表的总的长度
    //4 得到size 后，我们从链表的第一个开始遍历（size-index）个，就可以得到
    public static HeroNode findLastIndexNode(HeroNode head , int index){
        if (head.next == null){
            return null; //链表为空
        }
        //第一个遍历得到链表的长度
        int size = getLength(head);
        //第二次遍历 （size-index），就是倒数第 k个节点
        //先做一个校验
        if (index<0 || index>size){
            return null; //找不到
        }
        //定义一个辅助变量 , for循环定义到倒数的index
        HeroNode cur = head.next;
        for (int i=0; i<size-index ; i++){ //  3-2
            cur = cur.next;
        }
        return cur;
    }


    /**
     * 获取节点个数
     * @param head
     * @return
     */
    public static int getLength(HeroNode head){
        if (head.next == null){
            return 0;
        }
        int length = 0;
        //定义一个辅助的变量
        HeroNode cur = head.next;
        while (cur != null){
            length++;
            cur = cur.next;//遍历
        }
        return length;
    }


}

//定义SingLeLinkedList 管理英雄
class SingLeLinkedList{

    //先初始化一个 头节点，头节点不动 , 不存放具体的数据
    private HeroNode head = new HeroNode(0,"","");

    //get头节点
    public HeroNode getHead() {
        return head;
    }


    //添加节点到单向链表,添加到链表的尾部
    // 思路 ： 当不考虑编号的顺序时
    // 1 找到当前链表的最后节点 ； 2 将最后这个节点的next 指向 新的节点
    public void add(HeroNode heroNode){

        //因为 head不动 ，因此我们小一个辅助遍历 temp
        HeroNode temp = head;
        //遍历链表找到最后
        while (true){
            //当
            if (temp.next == null){
                break;
            }
            //如果没有找到最后 , 就将temp后移
            temp = temp.next;
        }
        //当退出while循环时， temp 就指向了链表的最后
        temp.next = heroNode;
    }


    /**
     * 第二种方式添加数据，按顺序插入
     */
    public void addByOrder(HeroNode heroNode){
        //因为头节点不能动，通过辅助变量来找到添加的位置
        //因为是但链表，因此找到的temp是位于 添加位置的前一个节点，否则插入不了
        HeroNode temp = head;
        boolean flag = false; //标识添加的编号是否存在，默认为false，存在了添加不了
        while (true){
            if (temp.next == null){ //说明temp已经在链表的最后,节点插入到链表尾部
                break; //
            }
            //位置找到了，在temp 和 temp.next 的位置之间插入
            if (temp.next.no > heroNode.no){  // 4 > 1  （2） ， 节点按顺序添加
                break;
            }else if (temp.next.no == heroNode.no){ //说明编号存在，添加不了

                flag = true; //说明编号存在
                break;
            }
            //temp往下移动，下一个再判断
            temp = temp.next; //后移判断后面的
        }

        //判断flag的值
        if (flag){ //true：说明编号存在，不能插入
            System.out.println("要插入的编号已经存在，不能加入："+ heroNode.no);
        }else {
            //插入到链表中 ， temp的后边
            heroNode.next = temp.next; // 指向的下一个节点替换（原来temp.next指向的下一个节点改换为heroNode.next指向）
            temp.next = heroNode; // temp.next后的数据替换为hernNode
        }
    }


    /**
     * 修改节点的信息，根据编号来修改，即编号不能修改
     */
    //根据 newHeroNoe 的no 来修改即可
    public void update(HeroNode newHeroNoe){
        //判断是否为空
        if (head.next == null){
            System.out.println("链表为空");
            return;
        }
        //找到需要修改的节点 ， 根据 no 编号
        //先定义一个辅助变量
        HeroNode temp = head.next;
        boolean flag = false; //表示没找打到该节点
        while (true){
            if (temp == null){
                break; //到链表的最后，没有找到要修改的节点
            }
            if (temp.no == newHeroNoe.no){ //找到了
                flag = true;
                break;
            }
            temp = temp.next;
        }

        //根据flag判断是否找到
        if (flag){
            //找到了，修改
            temp.name = newHeroNoe.name;
            temp.nickName = newHeroNoe.nickName;
        }else {
            //没有找到
            System.out.println("没有找到该编号的节点，不能修改:"+newHeroNoe.no);
        }

    }


    /**
     * 删除节点
     */
    // head节点不能动，需要一个temp赋值节点来找到要删除节点的前一个节点
    //说明比较的是 temp.next.no 和需要删除的节点的 no比较
    public void delete(int no){
        HeroNode temp = head;
        boolean flag = false;//表示没有找到删除节点的前一个节点
        while (true){
            if (temp.next == null){ //没有找到要删除的节点
                break;
            }
            if (temp.next.no == no){
                flag = true; //找到了
                break;
            }
            temp = temp.next;//后移
        }

        //判断flag
        if (flag){
            //找到，可以删除
            temp.next = temp.next.next;
        }else {
            System.out.println("没有找到要删除的节点，该节点不存在："+no);
        }
    }



    /**
     * 显示链表中的全部数据信息
     */
    public void list(){
        //先判断链表是否为空
        if (head.next == null){
            System.out.println("链表为空");
            return;
        }
        //因为头节点，不能动 ， 因此我们需要一个辅助遍历来遍历
        HeroNode temp = head.next;
        while (true){
            //判断是否是链表的最后
            if (temp == null){
                break;
            }
            //输出节点的信息
            System.out.println(temp);
            //将temp后移，一定要后移，否则会死循环
            temp = temp.next;
        }
    }


}


//定义HeroNode 每个HeroNode 对象就是一个节点
class HeroNode{

    public int no;
    public String name;
    public String nickName;
    public HeroNode next; //指向下一个节点

    public HeroNode(int no,String name,String nickName){
        this.no = no;
        this.name = name;
        this.nickName = nickName;
    }

    //为了显示方法，重写toString方法
    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nickName='" + nickName  +
                '}';
    }

}